分块简介

分块，其实不是数据结构，是一种思想，但常用于数据结构中，所以通常把分块当作数据结构来看待。

分块的主要思想就是将一段数列分为 n\sqrt{n} 块，进行修改和查询操作，有着 O(nn)O(n \sqrt{n}) 的时间复杂度。虽然效率不如线段树和树状数组的 O(nlog⁡n)O(n \log{n})，但比线段数更好调，也是它的一大优点。

算法简述

一开始先预处理出每个点所在块，一些可以自行加，比如某个块的左端点和右端点。

先讲修改操作。

修改操作

我们可以讲序列分为 O(n)O(\sqrt{n}) 块，然后可以分为 左端点所在块\color{blue}\text{左端点所在块}，右端点所在块\color{blue}\text{右端点所在块} 和 两个块之间包着的块\color{red}\text{两个块之间包着的块}。

对于两个块之间包着的块，一个一个块进行修改，对于左端点和右端点所在块，直接暴力修改即可。

至于为什么要分为 O(n)O(\sqrt{n}) 块，是因为根号平衡的思想，大部分的根号数据结构都是运用了根号平衡的思想。

void update(int l, int r, int k) {
	int lid = id[l], rid = id[r];
	for (int i = l; id[i] == lid && i <= r; i++)a[i] += k;
	for (int i = lid + 1; i < rid; i++)lazy[i] += k;//块的懒标记修改
	if (lid != rid)for (int i = r; id[i] == rid; i--)a[i] += k;
}

查询操作

与上面一个道理，用一个数组表示块的和，就不给参考的代码了，要注意查询点的时候有没有把懒标记加上去。

例题

例题 1 Lougu P3368 【模板】树状数组 2

P3368 【模板】树状数组 2

本来想放 P3372 【模板】线段树 1 的，但是 1≤N≤1051 \le N \le 10 ^ 5 水不掉，于是放了这个，其实道理都一样。

这么水就不放代码了吧。。。

例题2 Luogu P3870 [TJOI2009] 开关

P3870 [TJOI2009] 开关

同样很水，修改操作就是懒标记和点 xor⁡1\operatorname{xor} 1，然后求和。

那么也不放代码了吧 qwq。

例题3 Luogu P2801 教主的魔法

P2801 教主的魔法

分块开始有意思了。

修改操作就不多说了，重点讲一下如何求大于等于 CC 的人数。

用一个数组维护当前块所有人的身高，并且每个块都是单调不递减的，用于查询时进行二分。查询时仍然是先查询左右两边的散块，中间的用 lower_bound 或者手写二分求值。

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
const int N = 1e6 + 5;
int a[N], id[N], lazy[N], t[N];
int n, len;

void Sort(int k) {
	int l = (k - 1) * len + 1, r = min(k * len, n);
	for (int i = l; i <= r; i++)t[i] = a[i];
	sort(t + l, t + r + 1);
}

void update(int l, int r, int k) {
	int lid = id[l], rid = id[r];

	for (int i = l; id[i] == lid && i <= r; i++)a[i] += k;
	for (int i = lid + 1; i < rid; i++)lazy[i] += k;
	if (lid != rid)for (int i = r; id[i] == rid; i--)a[i] += k;

	Sort(lid); Sort(rid);
}

int query(int l, int r, int k) {
	int lid = id[l], rid = id[r], ans = 0;
	for (int i = l; id[i] == lid && i <= r; i++)if (a[i] + lazy[lid] >= k)ans++;

	for (int i = lid + 1; i < rid; i++)
		ans += i * len - (lower_bound(t + (i - 1) * len + 1, t + i * len + 1, k - lazy[i]) - t) + 1;

	if (lid != rid)for (int i = r; id[i] == rid; i--)if (a[i] + lazy[rid] >= k)ans++;
	return ans;
}

int main() {
	int T, l, r, k;
	char opt;
	cin >> n >> T;
	len = sqrt(n);
	memset(t, 0x3f3f3f3f, sizeof(t));

	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= n; i++)id[i] = (i - 1) / len + 1;
	for (int i = 1; i <= n; i++)t[i] = a[i];
	for (int i = 1; i <= int(ceil(n / len)); i++)sort(t + (i - 1) * len + 1, t + i * len + 1);

	while (T--) {
		cin >> opt >> l >> r >> k;
		if (opt == 'M')update(l, r, k);
		else cout << query(l, r, k) << endl;
	}
	return 0;
}

例题4 P4168 [Violet] 蒲公英

P4168 [Violet] 蒲公英

十分有意思的一道题。

如果不强制在线的话，就有莫队的一个做法，但是强制在线把莫队卡掉了，那怎么办？

首先，区间众数没有可加性，比如左边区间的众数是 11，右边的也是 11，两个区间合在一起就不一定是 11。

但凡有脑子的人都知道，答案 ans∈中间整块∪两边散块ans \in \text{中间整块}\cup\text{两边散块}

令 fl,rf_{l, r} 为第 ll 块到第 rr 块的众数，si,js_{i, j} 为第 11 块到第 ii 块 jj 的出现次数。

先预处理出 ff 和 ss 数组，设左端点所属块编号为 lidlid，右属块编号为 ridrid，ansans 初值为 flid,ridf_{lid, rid}，遍历两边散块，如果散块中的出现次数比答案出现次数大，更改答案。

/*Code By Manipula*/
#include <bits/stdc++.h>
// #define Fileopen
#pragma GCC optimize(2)
#define INF 0x3f3f3f3f
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, a, b) for (int i = (a); i >= (b); i--)
#define mst(arr, num) memset(arr, num, sizeof(arr))
#define max(x, y)((x) > (y) ? (x) : (y))
#define min(x, y)((x) < (y) ? (x) : (y))
#define swap(x, y) x ^= y ^= x ^= y
#define sqrt(n) pow(n, 0.5)
#define lowbit(x) (x & -x)
#define sort stable_sort
#define endl '\n'

using namespace std;

const int N = 4e4 + 5;
const int M = 205;

int f[M][M], s[M][N], l[M], r[M], id[N], a[N], b[N], B[N];
int n, T, tot, block, len, lstAns;

int query(int L, int R) {
	mst(B, 0); int lid = id[L], rid = id[R], ans = 0;

	if (rid - lid <= 1) {
		FOR(i, L, R) {
			if (++B[a[i]] > B[ans])ans = a[i];
			else if (B[a[i]] == B[ans] && a[i] < ans)ans = a[i];
		}
		return ans;
	}

	ans = f[lid + 1][rid - 1];

	FOR(i, L, r[lid])B[a[i]]++;
	FOR(i, l[rid], R)B[a[i]]++;

	FOR(i, L, r[lid]) {
		int _A = B[ans] + s[rid - 1][ans] - s[lid][ans], 
			_B = B[a[i]] + s[rid - 1][a[i]] - s[lid][a[i]];
		if (_A < _B)ans = a[i];
		else if (_A == _B && a[i] < ans)ans = a[i];
	}

	FOR(i, l[rid], R) {
		int _A = B[ans] + s[rid - 1][ans] - s[lid][ans], 
			_B = B[a[i]] + s[rid - 1][a[i]] - s[lid][a[i]];
		if (_A < _B)ans = a[i];
		else if (_A == _B && a[i] < ans)ans = a[i];
	}

	return ans;
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	cin >> n >> T; block = sqrt(n), len = ceil(1.0 * n / block);

	FOR(i, 1, n)id[i] = (i - 1) / block + 1;
	FOR(i, 1, len)l[i] = (i - 1) * block + 1;
	FOR(i, 1, len)r[i] = i * block;
	r[len] = len * block;

	FOR(i, 1, n)cin >> a[i];
	FOR(i, 1, n)b[i] = a[i];
	sort(b + 1, b + n + 1); tot = unique(b + 1, b + n + 1) - b - 1;
	FOR(i, 1, n)a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b; 

	FOR(i, 1, len) {
		mst(B, 0); int mode = 0;
		FOR(j, i, len) {
			FOR(k, l[j], r[j])
				if (++B[a[k]] > B[mode])mode = a[k];
				else if (B[a[k]] == B[mode] && a[k] < mode)mode = a[k];
			f[i][j] = mode;
		}
	}
	FOR(i, 1, len) {
		FOR(j, 1, tot)s[i][j] = s[i - 1][j];
		FOR(j, l[i], r[i])s[i][a[j]]++;
	}

	while (T--) {
		int L, R; cin >> L >> R;
		L = (L + lstAns - 1) % n + 1, R = (R + lstAns - 1) % n + 1;
		if (L > R)swap(L, R);
		cout << (lstAns = b[query(L, R)]) << endl;
	}
	return 0;
}

习题

Luogu P4135 作诗